A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, a s it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
1. Field
The present invention relates generally to computer graphics and, more specifically, to shape transformation of two-dimensional and three-dimensional objects on a computer display.
2. Description of Related Art
In recent years, image processing techniques, popularly known as xe2x80x9cmorphing,xe2x80x9d have achieved widespread use in the entertainment industry. Morphing involves the transformation of one image into another image or from one model into another model. Morphing operations can be performed to transform one two-dimensional (2-D) image into another 2-D image, to transform one 2-D model into another 2-D model, or to transform one three-dimensional (3-D) model into another 3-D model. These techniques specify some operation that maps points from one image or model onto points of the other image or model, and then simultaneously interpolate the color and position of corresponding points to generate intermediate images or models. When viewed in sequence, these intermediate images produce an animation of the first image or model changing into the second image or model. Variations of these techniques have been used to create special effects for television commercials, music videos, movies, and web pages on the World Wide Web.
Morphs are typically restricted to 2-D images, primarily because a realistic transition between two-dimensional (2-D) and three-dimensional (3-D) models is difficult to specify. However, such specifications might be valuable because the resulting morph can be viewed from arbitrary viewpoints in arbitrary settings, can be arbitrarily scaled and placed, and provides greater compression and realism.
There are at least two existing approaches for defining a morph between two 3-D models, each of which may be adapted for 2-D models. The first approach is described in xe2x80x9cShape Transformation For Polyhedral Objectsxe2x80x9d, by James R. Kent, et al., Computer Graphics, Vol. 26, No. 2, July, 1992. Kent, et al. describes a process that, given two 3-D polyhedral models, generates two new models that have the same or similar shape as the original ones, but that allow transformations from one to another to be easily computed. This process assumes the morphing of star-shaped objects only. If the objects are not star-shaped, then externally supplied information is employed to divide the non-star-shaped objects into several star-shaped objects for morphing. Star-shaped refers to models for which at least one interior point p exists such that any semi-infinite ray originating at p intersects the surface of the object at exactly one point. The second approach is discussed in xe2x80x9cSolid-Interpolating Deformations: Construction and Animation of PIPsxe2x80x9d, by Anil Kaul and Jarek Rossignac, Eurographics ""91, Proceedings of the European Computer Graphics Conference, September 1991, pp. 493-505. Kaul and Rossignac describe a process using an animation primitive called a Parameterized Interpolating Polyhedron (PIP), which may be animated on widely used graphic hardware because a PIP is a smoothly varying family of polyhedra representations bounded by faces that evolve with time. The faces have constant orientation and vertices that each move on a straight line between the vertex of the initial shape and a vertex of the final one. This process uses Minkowski sum operations for computing the PIPs.
There are several drawbacks to the above approaches. Both approaches exhibit a quadratic computational complexity, so they are impractical for some models. Furthermore, if two models to be morphed have N1 and N2 vertices, respectively, both approaches use O(N1*N2) storage units for storing the intermediate representations. Hence, as the models grow more complex, the storage used becomes very large. With the existing approaches, content developers cannot easily adjust or guide the construction of the morph at low resolutions. Further, content developers do not have control over the morphing process through exposable parameters or alternative sub-algorithms.
Thus, an improved method of morphing 2-D and 3-D models is desired that reduces the deficiencies and limitations of the prior art.
An embodiment of the present invention is a method of constructing morphs between a first model having a first resolution and a second model having a second resolution. The method includes determining a first morph between the first model and the second model, increasing resolution of at least one of the first and second models, and determining a subsequent morph between the first model and the second model.